package com.lili.math;

/**
 * @Auther: 李 力
 * @Date: 2024/8/2
 * @Description: 汉明距离总和
 * @version: 1.0
 */
public class LeetCode477 {
    /*
     * 时间复杂度: O(n^2-1)
     * 空间复杂度: O(1)
     */
    public static int totalHammingDistance(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                if (i != j) {
                    sum = sum + Integer.bitCount((nums[i]) ^ (nums[j]));
                }
            }
        }
        return sum;
    }

    /*
     * 时间复杂度: O(n*30)
     * 空间复杂度: O(1)
     */
    public static int totalHammingDistance2(int[] nums) {
        int ans = 0;
        int n = nums.length;
        for (int i = 0; i < 30; i++) {
            int c = 0;
            for (int val : nums) {
                c = c + (val >> i) & 1;
            }
            ans = ans + c * (n - c);
        }
        return ans;
    }
}
